package cn.xaut.查找表;

import java.util.*;

public class demo451 {

    // 数组代替哈希映射
    public String frequencySort2(String s) {
        
        char[] cs = s.toCharArray();
        int len = s.length();

        int[] freq = new int[128];
        for (char c : cs)
            freq[c] ++;

        // 定义一个大顶堆
        // 按字母出现的频率降序排列
        PriorityQueue<Character> pq = new PriorityQueue<>(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return freq[o2] - freq[o1];
            }
        });

        for (int i = 0; i < freq.length; i++) {
            if (freq[i] > 0)
                pq.offer((char) i);
        }
        
        StringBuilder sb = new StringBuilder();

        while (!pq.isEmpty()) {
            char c = pq.poll();
            while (freq[c]-- > 0)
                sb.append(c);
        }
        
        return sb.toString();
    }
    
    // 哈希映射
    public String frequencySort(String s) {

        char[] cs = s.toCharArray();
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < len; i++) 
            map.put(cs[i], map.getOrDefault(cs[i], 0) + 1);

        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();   // 按 Value 降序排列
            }
        });

        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            char key = entry.getKey();
            int value = entry.getValue();
            while (value-- > 0) 
                sb.append(key);
        }
        
        return sb.toString();
    }

    public static void main(String[] args) {

        System.out.println(new demo451().frequencySort2("tree"));//"eert"
        System.out.println(new demo451().frequencySort2("cccaaa"));//"cccaaa" or "aaaccc"
        System.out.println(new demo451().frequencySort2("Aabb"));//"bbAa" or "bbaA"
        System.out.println(new demo451().frequencySort2("raaeaedere"));//"eeeeaaarrd"
    }
}
